---
title: "4、方格填数"
created: 2025-11-28
tags:
  - 算法
---

# 4、方格填数

## 题目 [方格填数](https://www.lanqiao.cn/problems/664/learning/)

![[image-6794e66a.png]]

## 思路分析

可以直接全排列出来0~9的组合 再把每个数对应到格子里去比对

也可以像n皇后那样 从每个格子考虑 确定当前放什么 然后下一个格子能放什么……

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

string s="0123456789";

bool check(char a,char b){

  if(abs(int(a)-int(b))==1)

    return false;

  return true;

}

int main(){

  int cnt=0;

  do {

      if(

        check(s[0],s[1]) && check(s[0],s[3]) && check(s[0],s[4]) && check(s[0],s[5])

        &&

        check(s[1],s[2]) && check(s[1],s[4]) && check(s[1],s[5]) && check(s[1],s[6])

        &&

        check(s[2],s[5]) && check(s[2],s[6])

        &&

        check(s[3],s[4]) && check(s[3],s[7]) && check(s[3],s[8])

        &&

        check(s[4],s[5]) && check(s[4],s[7]) && check(s[4],s[8]) && check(s[4],s[9])

        &&

        check(s[5],s[6]) && check(s[5],s[8]) && check(s[5],s[9])

        &&

        check(s[6],s[9])

        &&

        check(s[7],s[8])

        &&

        check(s[8],s[9])

      )

        cnt++;

  }while (next_permutation(s.begin(), s.end()));

  cout<<cnt;

  return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

int a[4][5]={-20};

bool st[10];

int dx[4]={-1,-1,-1,0};

int dy[4]={0,1,-1,-1};

int sum;

bool check(int x,int y,int n){

  for(int i=0;i<4;i++){

    int nx=x+dx[i];

    int ny=y+dy[i];

    if(nx<3 && nx>=0 && ny>=0 && ny<4){

      if(abs(a[nx][ny]-n)==1)

        return false;

    }

  }

  return true;

}

void dfs(int x,int y){

  if(x==2 && y==3){

    sum++;

    return;

  }

  for(int i=0;i<10;i++){

    if(!st[i] && check(x,y,i)){

      st[i]=true;

      a[x][y]=i;

      if(y+1<4)

        dfs(x,y+1);

      else

        dfs(x+1,0);

      st[i]=false;

      a[x][y]=-20;

    }

  }

}

int main()

{

  dfs(0,1);

  cout<<sum;

  return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/DFS BFS相关模型/DFS/全排列（考虑顺序）/3、凑算式|3、凑算式]] 🏠 [[00-刷题理模型]] ➡️ [[三羊献瑞|三羊献瑞]]